package targetToOffer.eighteenthDay;

import java.util.Arrays;

/**
 * @author Godc
 * @description
 */
public class MajorityElement {
}
class Solution {
    // 1.排序法，排序后，超过一半的数一定在中间
    // 2.map法，较简单
    /**
     * 摩尔投票法
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        int num = 0,vote = 0;
        // 类似于同归于尽法，每次都是一换一，最后人多的队伍(众数)或者胜利
        for (int i = 0; i < nums.length; i++) {
            if(vote==0) num = nums[i];
            vote += num==nums[i]?1:-1;
        }
        return num;
    }
}